#include <stdio.h>

void exchange(int* i, int* j) {
	int temp;
	temp = *i;
	*i = *j;
	*j = temp;
}

void print(int* a, int size) {
	int i;
	for (i = 0; i < size; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}

void selection(int* a, int size) {
	int i, j, min;

	for (i = 0; i < size; i++) {
		min = i;
		for (j = i+1; j < size; j++) 
			if (a[min] > a[j])
				min = j;
		exchange(a+min, a+i);
		print(a, size);
	}
}

void insertion(int* a, int size) {
	int i, j;

	for (i = 0; i < size; i++) {
		for (j = i+1; j > 0; j--) {
			if (a[j] < a[j-1])
				exchange(a+j, a+j-1);
		}
		print(a, size);
	}
}

void bubble(int* a, int size) {
	int i, j;

	for (i = 0; i < size; i++) {
		for (j = size-1; j > i; j--) {
			if (a[j] < a[j-1])
				exchange(a+j, a+j-1);
		}
		print(a, size);
	}
}

int partition(int* a, int low, int high) {
	int temp;
	
	temp = a[low];
	while (low < high) {
		while (low < high && temp < a[high])
			high--;
		a[low] = a[high];
		while (low < high && temp > a[low])
			low++;
		a[high] = a[low];
	}
	a[low] = temp;
	return low;
}

void quick(int* a, int low, int high) {
	int index;

	if (low >= high) 
		return;
	index = partition(a, low, high);
	print(a, 9);
	quick(a, low, index-1);
	quick(a, index+1, high);
}

void main() {
	int a[] = {50, 30, 60, 90, 40, 21, 54, 44, 32};
	quick(a, 0, 8);
}
